package LeetCode.month01.day29;

import java.util.*;

public class No220 {
    public static void main(String[] args) {
        System.out.println(containsNearbyAlmostDuplicate(new int[]{1,2,3,1,2,1},3,0));
    }

    public static long getId(long a,long b){
        if(a>=0){
            return a/b;
        }
        return (a+1)/b-1;
    }
    public static boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        int n = nums.length;
        Map<Long,Long> map = new HashMap<>();
        long w = (long)valueDiff +1;
        for (int i = 0; i <n; i++) {
            long id = getId(nums[i],w);
            if(map.containsKey(id)){
                return true;
            }
            if(map.containsKey(id-1)&&Math.abs(map.get(id-1)-nums[i])<w){
                return true;
            }
            if(map.containsKey(id+1)&&Math.abs(map.get(id+1)-nums[i])<w){
                return true;
            }
            map.put(id,(long)nums[i]);
            if(i>=indexDiff) {
                map.remove(getId(nums[i-indexDiff],w));
            }
        }
        return false;

//        TreeSet<Long> set = new TreeSet<>();
//        int n = nums.length;
//        for (int i = 0; i < n; i++) {
//            if(set.ceiling((long)nums[i]-valueDiff)!=null){
//                long num = set.ceiling((long) nums[i]-valueDiff);
//                if(num<=nums[i]+valueDiff){
//                    return true;
//                }
//            }
//            set.add((long)nums[i]);
//            if(i>=indexDiff) set.remove((long)nums[i-indexDiff]);
//        }
//        return false;

//        int n = nums.length;
//        for (int k = 2; k <=indexDiff+1 ; k++) {
//            for (int i = 0; i <= n-k; i++) {
//                if(Math.abs(nums[i]-nums[i+k-1])<=valueDiff) return true;
//            }
//        }
//        return false;
    }
}
